package first.niuke.midding;

/**
 * @ClassName NC109
 * @description:
 * @author: 荣燊
 * @create: 2021-06-16 16:56
 **/
public class NC109 {
    // 岛屿数量

    public static void main(String[] args) {
        char[][] test = {{'1','1','0','0','0'},
                        {'0','1','0','1','1'},
                        {'0','0','0','1','1'},
                        {'0','0','0','0','0'},
                        {'0','0','1','1','1'}};
//        dfs(test, 0, 0);
//        for (int i=0; i<test.length; i++) {
//            System.out.println("");
//            for (int j=0; j<test[0].length; j++) {
//                System.out.print(test[i][j]+" ");
//            }
//        }
        System.out.println(solve(test));
    }

    public static int solve (char[][] grid) {
        // write code here
        if (grid == null || grid.length == 0) {
            return 0;
        }

        int result = 0;

        for (int i=0; i<grid.length; i++) {
            for (int j=0; j<grid[0].length; j++) {
                if (grid[i][j] == '1') {
                    result++;
                    dfs(grid, i, j);
                }
            }
        }

        return result;
    }

    // 将第一次遍历到的岛屿全为0
    public static void dfs(char[][] grid, int r, int l) {
        int longLength = grid.length;
        int wideLength = grid[0].length;

        // r:左右，l上下
        if (r < 0 || l < 0 || r >= longLength || l >= wideLength || grid[r][l] == '0') {
            return;
        }

        // 当grid[r][l] == '1'赋值为0
        grid[r][l] = '0';
        dfs(grid, r-1, l);
        dfs(grid, r+1, l);
        dfs(grid, r, l-1);
        dfs(grid, r, l+1);
    }
}
